package main.leetcode.competition.weeklycomp.competition181;

/**
 * 5366.检查网络中是否存在有效路径
 *
 * <p>给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是：
 *
 * <p>1 表示连接左单元格和右单元格的街道。 2 表示连接上单元格和下单元格的街道。 3 表示连接左单元格和下单元格的街道。 4 表示连接右单元格和下单元格的街道。 5
 * 表示连接左单元格和上单元格的街道。 6 表示连接右单元格和上单元格的街道。
 *
 * <p>你最开始从左上角的单元格 (0,0) 开始出发，网格中的「有效路径」是指从左上方的单元格 (0,0) 开始、一直到右下方的 (m-1,n-1) 结束的路径。该路径必须只沿着街道走。
 *
 * <p>注意：你 不能 变更街道。
 *
 * <p>如果网格中存在有效的路径，则返回 true，否则返回 false 。
 *
 * <p>提示：m == grid.length n == grid[i].length 1 <= m, n <= 300 1 <= grid[i][j] <= 6
 */
public class Solution3 {
    public static void main(String[] args) {
        System.out.println(
                new Solution3()
                        .hasValidPath(
                                new int[][] {
                                    // {2, 4, 3}, {6, 5, 2}
                                    // {1, 1, 1, 1, 1, 1, 3}
                                    {1, 1, 2}
                                }));
    }

    // 1 表示连接左单元格和右单元格的街道。
    // 2 表示连接上单元格和下单元格的街道。
    // 3 表示连接左单元格和下单元格的街道。
    // 4 表示连接右单元格和下单元格的街道。
    // 5 表示连接左单元格和上单元格的街道。
    // 6 表示连接右单元格和上单元格的街道。
    public boolean hasValidPath(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] isVisited = new boolean[m][n];
        return dfs(grid, isVisited, m, n, 0, 0, 0);
    }

    private boolean dfs(
            int[][] grid, boolean[][] isVisited, int m, int n, int i, int j, int expect) {
        if (i < 0
                || i > m - 1
                || j < 0
                || j > n - 1
                || isVisited[i][j]
                || !isExpect(grid[i][j], expect)) return false;
        if (i == m - 1 && j == n - 1) return true;
        int dir = grid[i][j];
        isVisited[i][j] = true;
        switch (dir) {
            case 1:
                return dfs(grid, isVisited, m, n, i, j - 1, 3) // 左
                        || dfs(grid, isVisited, m, n, i, j + 1, 4); // 右
            case 2:
                return dfs(grid, isVisited, m, n, i - 1, j, 1) // 上
                        || dfs(grid, isVisited, m, n, i + 1, j, 2); // 下
            case 3:
                return dfs(grid, isVisited, m, n, i, j - 1, 3) // 左
                        || dfs(grid, isVisited, m, n, i + 1, j, 2); // 下
            case 4:
                return dfs(grid, isVisited, m, n, i, j + 1, 4) // 右
                        || dfs(grid, isVisited, m, n, i + 1, j, 2); // 下
            case 5:
                return dfs(grid, isVisited, m, n, i, j - 1, 3) // 左
                        || dfs(grid, isVisited, m, n, i - 1, j, 1); // 上
            case 6:
                return dfs(grid, isVisited, m, n, i, j + 1, 4) // 右
                        || dfs(grid, isVisited, m, n, i - 1, j, 1); // 上
            default:
                return false;
        }
    }

    private boolean isExpect(int val, int dir) {
        if (dir == 0) return true;
        if (dir == 1) return val == 2 || val == 3 || val == 4; // 上
        if (dir == 2) return val == 2 || val == 5 || val == 6; // 下
        if (dir == 3) return val == 1 || val == 4 || val == 6; // 左
        if (dir == 4) return val == 1 || val == 3 || val == 5; // 右
        return false;
    }
}
